% !TEX root = disc2012.tex
\section{Algorithm for $k$ Random Walks}\label{sec:k-algo}
\vspace{-0.05in}
The previous section was devoted to performing a single random walk of length $\tau$ (mixing time) efficiently to sample from the stationary distribution. In many applications, one typically requires a large number of random walk samples. A larger amount of samples allows for a better estimation of the problem at hand. In this section we focus on obtaining several random walk samples.  Specifically, we consider the scenario when we want to compute $k$ independent walks each of
length $\tau$ from different (not necessarily distinct) sources $s_1, s_2, \ldots, s_k$. We show that {\sc Single-Random-Walk} can be extended to solve this problem. In particular, the algorithm {\sc Many-Random-Walks} (for full pseudocode cf. Algorithm $2$ in the full version of the paper \cite{SMP12}) to compute $k$ walks is essentially repeating the {\sc Single-Random-Walk} algorithm on each source with one common/shared phase, and yet through overlapping computation, completes faster than $k$ times the previous bound. The crucial observation is that we have to do Phase 1 only once and still ensure all walks are independent. The pseudo code of the algorithm, analysis and proof of the main result is included in the full version of the paper \cite{SMP12} due to space limitation. 

\iffalse
\vspace{-0.06in}
\paragraph{{\sc Many-Random-Walks} :} Let $\lambda=(32 \sqrt{k\tau \Phi+1}\log n+k)(\log n)^2$. If
$\lambda \ge \tau$ then run the naive random walk algorithm. %, i.e., the sources find walks of length $\tau$ simultaneously by sending tokens. 
Otherwise, do the following. First, modify Phase~2 of {\sc Single-Random-Walk} to create multiple walks, one at a time; i.e., in the second phase, we stitch the short walks together to get a
walk of length $\tau$ starting at $s_1$ then do the same thing for $s_2$, $s_3$, and so on. We show that {\sc Many-Random-Walks} algorithm finishes in $\tilde O\left(\min(\sqrt{k\tau \Phi}, k+\tau)\right)$ rounds with high probability. This result is also stated in the Theorem \ref{thm:kwalks} (Section \ref{sec:results}). Since the details of this specific extension is similar to the previous ideas even for the dynamic setting, the formal proofs are placed in the Appendix (Section \ref{multiple walks}).

\fi
%\begin{theorem}\label{thm:kwalks} {\sc Many-Random-Walks} finishes in
%$\tilde O\left(\min(\sqrt{k\tau \Phi}, k+\tau)\right)$
%rounds with high probability.
%\end{theorem}
%\begin{proof}
%See Section \ref{multiple walks} in Appendix.
%\end{proof}
